﻿<HTML>

<HEAD>
  <META HTTP-EQUIV="Content-Type" CONTENT="text/html; charset=utf-8" />  
  <TITLE>Algorithms, Solvers and Configuration Files</TITLE>
  <LINK HREF="doc.css" REL=STYLESHEET>
</HEAD>


<BODY>


<!-- ============================================ -->


  <H1>Algorithms, Solvers and Configuration Files</H1>

  <A HREF="heo.html">[Previous]</A><A HREF="projects.html">[Next]</A><A HREF="../index.html">[Home]</A>

  <H2>Contents</H2>

  <UL>
    <LI><A HREF="#overview">Overview</A></LI>
    <LI><A HREF="#ga">GA (Genetic Algorithm)</A></LI> 
    <LI><A HREF="#sa">SA (Simulated Annealing)</A></LI> 
  </UL>


<!-- ============================================ -->


  <A NAME="overview"></A>
  <H3>Overview</H3>

  <P>
    As it was mentioned in the previous section, two optimization methods are implemented in the library: GA and SA.
    Solvers implement these methods using different parallel programming techniques: MPI or OpenMP.
    At present, there are four solvers in the library: <TT>GA_MPI</TT>, <TT>GA_OMP</TT>, <TT>SA_MPI</TT>, <TT>SA_OMP</TT>.
  </P>

  <P>
    The behavior of the solvers is controlled by the configuration files with the <TT>*.ini</TT> extension by default.
    These files have the <TT>'parameter&nbsp;=&nbsp;value'</TT> format. 
    Some of these parameters are algorithm-specific, some are problem-specific, and the others are common to all optimization methods and solvers.
  </P>

  <P>
    The description of the parameters that are common to all solvers is given in the table below.
  </P>


  <TABLE>
    <TBODY>
      <TR>
        <TH>Parameter</TH>
        <TH>Type</TH>
        <TH>Description</TH>
        <TH>Default Value</TH>
      </TR>

      <TR>
        <TD>run_count</TD>
        <TD ALIGN="center">int</TD>
        <TD>Number of the solver runs</TD>
        <TD ALIGN="center">1</TD>
      </TR>


      <TR>
        <TD>max_step</TD>
        <TD ALIGN="center">int</TD>
        <TD>Maximum number of iterations</TD>
        <TD ALIGN="center">100</TD>
      </TR>


      <TR>
        <TD>rand_seed</TD>
        <TD ALIGN="center">int</TD>
        <TD>Random seed</TD>
        <TD ALIGN="center">1100101</TD>
      </TR>


      <TR>
        <TD>debug_level</TD>
        <TD ALIGN="center">int</TD>
        <TD>Debug level: 0 &mdash; low verbosity; 1 &mdash; high verbosity.</TD>
        <TD ALIGN="center">1</TD>
      </TR>
    </TBODY>
  </TABLE>

  <P>
  </P>

<!-- ============================================ -->


  <A NAME="ga"></A>
  <H3>GA (Genetic Algorithm)</H3>

  <P>
    The genetic algorithm (GA) is a well-known optimization technique that describes the optimization process in terms of the evolving population of chromosomes.
    The sequential version of this algorithm is shown below:
  </P>

  <DIV CLASS="code">
    &nbsp;1: <I>Population</I> := InitialPopulation()<BR>
    &nbsp;2: <B>for all</B> &alpha;<SUB>i</SUB>&isin;<I>Population</I> <B>do</B><BR>
    &nbsp;3: &nbsp;&nbsp;EvaluateFitness(&alpha;<SUB>i</SUB>)<BR>
    &nbsp;4: <B>end for</B><BR>
    &nbsp;5: <B>while not</B> StopCondition() <B>do</B><BR>
    &nbsp;6: &nbsp;&nbsp;<I>Parents</I> := SelectParents(<I>Population</I>)<BR>
    &nbsp;7: &nbsp;&nbsp;<I>Offspring</I> := Crossover(<I>Parents</I>)<BR>
    &nbsp;8: &nbsp;&nbsp;<I>Offspring</I> := Mutation(<I>Offspring</I>)<BR>
    &nbsp;9: &nbsp;&nbsp;<B>for all</B> &beta;<SUB>i</SUB>&isin;<I>Offspring</I> <B>do</B><BR>
         10: &nbsp;&nbsp;&nbsp;&nbsp;EvaluateFitness(&beta;<SUB>i</SUB>)<BR>
         11: &nbsp;&nbsp;<B>end for</B><BR>
         12: &nbsp;&nbsp;<I>Population</I> := UpdatePopulation(<I>Parents</I>&cup;<I>Offspring</I>)<BR>
         13: <B>end while</B><BR>
         14: <I>Solution</I> := ChooseBestOf(<I>Population</I>)<BR>
    <B>Ensure:</B> <I>Solution</I>
  </DIV>


  <P>
    There exist several parallel models of this optimization method.
  </P> 

  <P>
    The <TT>GA_MPI</TT> solver implements the island model of the GA.
    In this model separate populations (islands) of the same size are evolved by concurrently running threads that periodically cooperate with each other.
  </P> 

  <P>
    The <TT>GA_OMP</TT> solver implements the global population model.
    In this model all threads work on one and the same population.
  </P> 

  <P>
    The following table lists the GA parameters. 
  </P>


  <TABLE>
    <TBODY>
      <TR>
        <TH>Parameter</TH>
        <TH>Type</TH>
        <TH>Description</TH>
        <TH>Default Value</TH>
      </TR>

      <TR>
        <TD>population_size</TD>
        <TD ALIGN="center">int</TD>
        <TD>Population size. In the island model this parameter indicates the population size for each island.</TD>
        <TD ALIGN="center">30</TD>
      </TR>

      <TR>
        <TD>offspring_size</TD>
        <TD ALIGN="center">int</TD>
        <TD>Offspring size. In the island model this parameter indicates the offspring size for each island.</TD>
        <TD ALIGN="center">50</TD>
      </TR>

      <TR>
        <TD>parent_selection</TD>
        <TD ALIGN="center">int</TD>
        <TD>Parent selection type: 0 &mdash; tournament selection; 1 &mdash; roulette selection; 2 &mdash; random selection.</TD>
        <TD ALIGN="center">1</TD>
      </TR>

      <TR>
        <TD>offspring_selection</TD>
        <TD ALIGN="center">int</TD>
        <TD>Offspring selection type: 0 &mdash; tournament selection; 1 &mdash; roulette selection; 2 &mdash; random selection.</TD>
        <TD ALIGN="center">0</TD>
      </TR>
 
      <TR>
        <TD>tournament_size</TD>
        <TD ALIGN="center">int</TD>
        <TD>Tournament size.</TD>
        <TD ALIGN="center">4</TD>
      </TR>
 
      <TR>
        <TD>crossover_probability</TD>
        <TD ALIGN="center">double</TD>
        <TD>Crossover probability.</TD>
        <TD ALIGN="center">0.3</TD>
      </TR>
 
      <TR>
        <TD>mutation_probability</TD>
        <TD ALIGN="center">double</TD>
        <TD>Mutation probability.</TD>
        <TD ALIGN="center">0.003</TD>
      </TR>
 
      <TR>
        <TD>mutation_fadeout</TD>
        <TD ALIGN="center">bool</TD>
        <TD>Mutation probability fadeout.</TD>
        <TD ALIGN="center">false</TD>
 
      <TR>
        <TD>only_offspring</TD>
        <TD ALIGN="center">bool</TD>
        <TD>Select only offspring into the next population.</TD>
        <TD ALIGN="center">false</TD>
 
      <TR>
        <TD>async_mode</TD>
        <TD ALIGN="center">bool</TD>
        <TD>Asynchronous cooperation mode for the island model.</TD>
        <TD ALIGN="center">true</TD>
      </TR>
 
      <TR>
        <TD>migration_size</TD>
        <TD ALIGN="center">int</TD>
        <TD>Migration size for the island model.</TD>
        <TD ALIGN="center">3</TD>
      </TR>
 
      <TR>
        <TD>migration_rate</TD>
        <TD ALIGN="center">int</TD>
        <TD>Migration rate for the island model.</TD>
        <TD ALIGN="center">25</TD>
      </TR>
   </TBODY>
  </TABLE>

  <P>
  </P>


<!-- ============================================ -->


  <A NAME="sa"></A>
  <H3>SA (Simulated Annealing)</H3>

 
  <P>
     The simulated annealing (SA) exploits an analogy between two processes: the process of obtaining low-energy states of a solid and the search for a minimum in a discrete system.
    It may be sketched in pseudocode as follows:
  </P> 

  <DIV CLASS="code">
    &nbsp;1: <I>Solution</I> := InitialSolution()<BR>
    &nbsp;2: <I>BestSolution</I> := <I>Solution</I><BR>
    &nbsp;3: <I>BestCost</I> := Cost(<I>Solution</I>)<BR>
    &nbsp;4: <I>T</I> := InitialTemperature()<BR>
    &nbsp;5: <I>k</I> := 0<BR>
    &nbsp;6: <B>while not</B> StopCondition() <B>do</B><BR>
    &nbsp;7: &nbsp;&nbsp;<I>NewSolution</I> := ChooseRandomOf(Neighborhood(<I>Solution</I>))<BR>
    &nbsp;8: &nbsp;&nbsp;<I>NewSolution</I> := Cost(<I>Solution</I>)<BR>
    &nbsp;9: &nbsp;&nbsp;<B>if</B> <I>NewCost</I> < <I>BestCost</I> <B>then</B><BR>
         10: &nbsp;&nbsp;&nbsp;&nbsp;<I>BestSolution</I> := <I>NewSolution</I><BR>
         11: &nbsp;&nbsp;&nbsp;&nbsp;<I>BestCost</I> := <I>NewCost</I><BR>
         12: &nbsp;&nbsp;<B>end if</B><BR>
         13: &nbsp;&nbsp;<I>Solution</I> := AcceptWithProbability(<I>Solution</I>, <I>NewSolution</I>, <I>T</I>)<BR>
         14: &nbsp;&nbsp;<I>k</I> := <I>k</I> + 1<BR>
         15: &nbsp;&nbsp;<I>T</I> := UpsateTemperature(<I>T</I>, <I>k</I>)<BR>
         16: <B>end while</B><BR>
    <B>Ensure:</B> <I>BestSolution</I>
  </DIV>


  <P>
    The <TT>SA_MPI</TT> and <TT>SA_OMP</TT> solvers implement the multistart model of the SA. 
    This model consists in running several cooperative SA that exchange information during execution.
  </P> 

  <P>
    The SA parameters are given in the table below. 
  </P>


  <TABLE>
    <TBODY>
      <TR>
        <TH>Parameter</TH>
        <TH>Type</TH>
        <TH>Description</TH>
        <TH>Default Value</TH>
      </TR>

      <TR>
        <TD>move_probability</TD>
        <TD ALIGN="center">double</TD>
        <TD>Move probability.</TD>
        <TD ALIGN="center">0.02</TD>
      </TR>

      <TR>
        <TD>initial_temperature</TD>
        <TD ALIGN="center">double</TD>
        <TD>Initial temperature.</TD>
        <TD ALIGN="center">1.0</TD>
      </TR>

      <TR>
        <TD>cooling_rate</TD>
        <TD ALIGN="center">double</TD>
        <TD>Cooling rate.</TD>
        <TD ALIGN="center">0.994</TD>
      </TR>

      <TR>
        <TD>heating_rate</TD>
        <TD ALIGN="center">double</TD>
        <TD>Heating rate.</TD>
        <TD ALIGN="center">1.5</TD>
      </TR>

      <TR>
        <TD>isotherm_moves</TD>
        <TD ALIGN="center">int</TD>
        <TD>Number of moves for each isotherm.</TD>
        <TD ALIGN="center">20</TD>
      </TR>
 
      <TR>
        <TD>async_mode</TD>
        <TD ALIGN="center">bool</TD>
        <TD>Asynchronous cooperation mode.</TD>
        <TD ALIGN="center">true</TD>
      </TR>
 
      <TR>
        <TD>cooperation_rate</TD>
        <TD ALIGN="center">int</TD>
        <TD>Cooperation rate.</TD>
        <TD ALIGN="center">25</TD>
      </TR>
    </TBODY>
  </TABLE>

  <P>
  </P>


<H2>&nbsp;</H2>

<A HREF="heo.html">[Previous]</A><A HREF="projects.html">[Next]</A><A HREF="../index.html">[Home]</A>


<!-- ============================================ -->


</BODY>

</HTML>


